package main

// 5. 最长回文子串
func main() {
	ss := []string{
		"babad",
		"cbbd",
	}
	for _, s := range ss {
		palindrome := longestPalindrome(s)
		println(palindrome)
	}
}

func longestPalindrome(s string) string {
	// 使用dp dp[i][j] 表述 是否 回文子串
	sLen := len(s)
	maxLen := 1
	idx := 0

	dp := make([][]bool, sLen)
	for i := 0; i < sLen; i++ {
		dp[i] = make([]bool, sLen)
	}

	for i := 0; i < sLen; i++ {
		dp[i][i] = true
	}

	for i := 1; i < sLen; i++ {
		for j := i - 1; j >= 0; j-- {
			if i-j >= 2 {
				dp[j][i] = dp[j+1][i-1] && s[j] == s[i]
			} else {
				dp[j][i] = s[j] == s[i]
			}
			if dp[j][i] && i-j+1 > maxLen {
				maxLen = i - j + 1
				idx = j
			}
		}
	}

	return s[idx : idx+maxLen]
}

/**
给你一个字符串 s，找到 s 中最长的
回文

子串

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成
*/
